//
//  BinaryTreeNode_convenience.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/20.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension BinaryTreeNode {
    
    var isRoot: Bool {
        return parent == nil
    }
    
    var isLchild: Bool {
        return !isRoot && parent?.lchild === self
    }
    
    var isRchild: Bool {
        return !isRoot && parent?.rchild === self
    }
    
    var hasParent: Bool {
        return !isRoot
    }
    
    var hasLchild: Bool {
        return lchild != nil
    }
    
    var hasRchild: Bool {
        return rchild != nil
    }
    
    var hasChild: Bool {
        return hasLchild || hasRchild
    }
    
    var hasBothChild: Bool {
        return hasLchild && hasRchild
    }
    
    var isLeaf: Bool {
        return !hasChild
    }
    
    var sibling: BinaryTreeNode<Element>? {
        return isLchild ? parent?.rchild : parent?.lchild
    }
    
    var uncle: BinaryTreeNode<Element>? {
        return parent?.sibling
    }
    
    // 理想平衡 左右子树高度相等
    var isBalanced: Bool {
        return stature(lchild) == stature(rchild)
    }
    // 平衡因子
    var balanceFactor: Int {
        return stature(lchild) - stature(rchild)
    }
    // AVL树左右子树高度差不超过1
    var isAvlBalanced: Bool {
        return abs(Int32(balanceFactor)) <= 1
    }
}

func stature<E>(_ p: BinaryTreeNode<E>?) -> Int {
    return (p != nil) ? p!.height : -1
}
